//
// Created by buyongjiu on 2024/4/21.
//

#include <iostream>
#include "../include/DFA.h"

int DFA::createDFA(NFA &nfa) {
    this->alphabet = nfa.alphabet;
    this->alphabet.erase("%");
    std::set<std::string> nowHaveState;
    std::map<std::string, bool> haveUse;
    // build the start state
    std::set<NFA_struct *> beg;
    beg.insert(nfa.Structs[0]);
    assert(0 == this->closure_(nfa, beg));
    auto beg_str = this->subSetsTostr(beg);
    nowHaveState.insert(beg_str);
    auto* p = new DFA_struct(START, beg_str);
    this->Structs.push_back(p);
    this->nameToStruct[beg_str] = p;
    this->state.insert(beg_str);
    std::vector<std::vector<std::string>> nextState;
    while(true) {
        bool done = true;
        for(auto &state: nowHaveState) {
            if(!haveUse[state]) {
                done = false;
                break;
            }
        }
        if(done) {
            break;
        }
        std::string cur = "";
        for(auto &state: nowHaveState) {
            if(!haveUse[state]) {
                cur = state;
                break;
            }
        }
        haveUse[cur] = true;
        auto cur_set = this->strTosubSets(nfa, cur);
        for(auto &edge: this->alphabet) {
            auto newState = move_(nfa, cur_set, edge);
            if(newState.empty()) {
                continue;
            }
            assert(0 == this->closure_(nfa, newState));
            auto new_str = this->subSetsTostr(newState);
            // 空集合
            if(new_str == "%") {
                continue;
            }
            if(nowHaveState.find(new_str) == nowHaveState.end()) {
                nowHaveState.insert(new_str);
            }
            nextState.push_back({cur, edge, new_str});
        }
    }
    for(auto& st: nowHaveState) {
        if(this->state.find(st) != this->state.end()) {
            continue;
        }
        this->state.insert(st);
        if(st.find("END") != std::string::npos) {
            p = new DFA_struct(END, st);
        } else {
            p = new DFA_struct(NORMAL, st);
        }
        this->Structs.push_back(p);
        this->nameToStruct[st] = p;
    }
    for(auto& edge: nextState) {
        this->nameToStruct[edge[0]]->addEdge(edge[1], edge[2]);
    }
    return 0;
}

std::set<NFA_struct *> DFA::move_(NFA &nfa, std::set<NFA_struct *> cur, std::string input) {
    std::set<NFA_struct *> ret;
    for(auto &a: cur) {
        if(a->gotoState.count(input) <= 0) {
            continue;
        }
        for(auto &next: a->gotoState[input]) {
            ret.insert(nfa.nameToStruct[next]);
        }
    }
    return ret;
}

int DFA::closure_(NFA &nfa, std::set<NFA_struct *> &cur) {
    int size = 0;
    while(true) {
        if(size == cur.size()) {
            break;
        }
        size = cur.size();
        for(auto &s: cur) {
            if(s->gotoState.count("%") <= 0) {
                continue;
            }
            for(auto &next: s->gotoState["%"]) {

                cur.insert(nfa.nameToStruct[next]);
            }
        }
    }
    return 0;
}

std::string DFA::subSetsTostr(const std::set<NFA_struct *> &subSets) {
    if(subSets.empty()) {
        return "%";
    }
    std::string str = "";
    for(auto& p: subSets) {
        str += p->nowState;
        str += "_";

    }
    return str;
}

std::set<NFA_struct *> DFA::strTosubSets(NFA &nfa, std::string str) {
    std::set<NFA_struct *> subSets;
    std::string tmp;
    for(auto& c: str) {
        if('_' == c) {
            subSets.insert(nfa.nameToStruct[tmp]);
            tmp = "";
        } else {
            tmp += c;
        }
    }
    return subSets;
}

void DFA::PrintDFA() {
    std::cout << "DFA Information:" << std::endl;
    std::cout << "Alphabet: ";
    for (const auto& symbol : alphabet) {
        std::cout << symbol << " ";
    }
    std::cout << std::endl;

    std::cout << "DFA States:" << std::endl;
    for (const auto& entry : nameToStruct) {
        std::cout << "State: " << entry.first << std::endl;
        std::cout << "Type: " << entry.second->type << std::endl;
        std::cout << "Transitions:" << std::endl;
        for (const auto& transition : entry.second->gotoState) {
            std::cout << "Input: " << transition.first << ", Next State: " << transition.second << std::endl;
        }
    }
}

bool DFA::accept(std::string str) {
    std::string cur = this->Structs[0]->nowState;
    for(auto& c: str) {
        std::string sc = "";
        sc += c;
        if(this->alphabet.find(sc) == this->alphabet.end()) {
            return false;
        }
        if(this->nameToStruct[cur]->gotoState.count(sc) <= 0) {
            return false;
        }
        cur = this->nameToStruct[cur]->gotoState[sc];
    }
    if(cur.find("END") != std::string::npos) {
        return true;
    }
    return false;
}

DFA_struct::DFA_struct(Type_t t, std::string nowstate) {
    this->type = t;
    this->nowState = nowstate;

}

int DFA_struct::addEdge(std::string &input, std::string &next) {
    this->gotoState[input] = next;
    return 0;
}
